﻿// -----------------------------------------------------------------------
// <copyright file="SalesmanSolver.cs" company="spbsu">
// Alexander Ulitin alexander.a.ulitin@gmail.com
// </copyright>
// -----------------------------------------------------------------------

namespace NeuronDotNet.Samples.TspSolver
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// Precisely solves salesman problem
    /// </summary>
    public class SalesmanSolver
    {
        private readonly double[,] citiesLinks;

        private readonly int citiesCount;

        private double foundedMin;

        private int[] foundedSolution;

        public double FoundedMin
        {
            get
            {
                return this.foundedMin;
            }
        }

        public int[] FoundedSolution
        {
            get
            {
                return this.foundedSolution;
            }
        }

        public SalesmanSolver(double[,] citiesLinks)
        {
            if (citiesLinks == null) 
                throw new ArgumentNullException();
            if(citiesLinks.GetLength(0) != citiesLinks.GetLength(1))
                throw new ArgumentException("citiesLinks");

            this.citiesLinks = citiesLinks;
            citiesCount = citiesLinks.GetLength(0);
            foundedMin = int.MaxValue;
        }

        public int[] Solve()
        {
            var path = new List<int>(citiesCount) { 0 };
            this.Travel(path);

            return foundedSolution;
        }

        private void Travel(IList<int> currentPath)
        {
            int lastCity = currentPath.Last();

            if(currentPath.Count == citiesCount)
            {
                double rating = CalculateRating(currentPath);
                if(rating < foundedMin)
                {
                    this.foundedMin = rating;
                    foundedSolution = currentPath.ToArray();
                }
            }

            var notUsedNumbers = Enumerable.Range(0, this.citiesCount)
                .Except(currentPath)
                .OrderBy(a => citiesLinks[lastCity, a]);
            
            currentPath.Add(0);
            foreach (var city in notUsedNumbers)
            {
                currentPath[currentPath.Count - 1] = city;
                if(this.CalculatePartialRating(currentPath) < foundedMin)
                {
                    this.Travel(currentPath);
                }
            }
            currentPath.RemoveAt(currentPath.Count - 1);
        }

        private double CalculatePartialRating(IList<int> currentPath)
        {
            double sum = 0;
            for (int i = 0; i < currentPath.Count - 1; i++)
            {
                sum = sum + citiesLinks[currentPath[i], currentPath[i + 1]];
            }
            return sum;
        }

        private double CalculateRating(IList<int> currentPath)
        {
            double sum = citiesLinks[currentPath.Last(), currentPath.First()];
            for (int i = 0; i < currentPath.Count - 1; i++)
            {
                sum = sum + citiesLinks[currentPath[i], currentPath[i + 1]];
            }
            return sum;
        }
    }
}
